## ALGORITHMS FOR THE ASSIGNMENT PROBLEM

### Introduction

With this package, I provide some MATLAB-functions regarding the rectangular assignment problem. This problem appears for example in tracking applications, where one has M existing tracks and N new measurements. For each possible assignment, a cost or distance is computed. All cost values form a matrix, where the row index corresponds to the tracks and the column index corresponds to the measurements. The provided functions return an optimal or suboptimal assignment - in the sense of minimum overall costs - for the given matrix.
In the process of gating, typically very unlikely assignments are forbidden. The given functions can handle forbidden assignments, which are marked by setting the corresponding assignment cost to infinity.
The optimal solution is computed using Munkres algorithm, also known as Hungarian Algorithm.

### Thanks

I have spent many hours to develop this package. If you would like to let me know that you appreciate my work, you can do so by leaving a donation.

### Functions contained in this package

assignmentallpossible.m
Computes the optimal assignment by recursively stepping over all possible assignment vectors. Used for reference computation.
assignmentoptimal.m and assignmentoptimal.c
Computes the optimal assignment (minimum overall costs) using Munkres algorithm.
assignmentsuboptimal1.m and assignmentsuboptimal1.c
Computes a suboptimal solution. Good for cases with many forbidden assignments.
assignmentsuboptimal2.m and assignmentsuboptimal2.c
Computes a suboptimal solution. Good for cases without forbidden assignments.
testassign.m
Compares the algorithms regarding performance and optimality of solutions.

### Usage

The first four functions are called like the following:
[assignment, cost] = assignment_xx(distMatrix);
(Replace "_xx" by "optimal", for example). Type "help assignment_xx" for more hints to the different algorithms.
Take care that all costs/distances are positive or zero!

### How to use mex-files

The C language source files are so-called mex-files for MATLAB. You should be able to compile these functions manually on all systems by typing
mex assignmentoptimal.c
mex assignmentsuboptimal1.c
mex assignmentsuboptimal2.c
in MATLAB. If you have never used the mex-command before, you first have to select a compiler. I suggest to use one of the built-in compilers that come with Matlab.
The mex-command creates a file with a system-dependent extension, in Windows it is .mexw32. As soon as this file in generated, you can use it as you would call a MATLAB function. When both mex- and m-file of the same name are on the MATLAB path, the mex-file is chosen.
The mex-files can save computation time up to a factor of 10 or 20. Use the test functions testassignment.m with your own preferences and have a look at the profiler output.
By the way, you will find that in some cases the mex-implementations of the suboptimal algorithms need a longer computation time than the optimal algorithm. The functions are much faster than the MATLAB-implementations, but they can still be improved (If you do, please let me know).

### Using the functions from C

The mex-files always contain a function called "mexFunction" that is needed for MATLAB and a function called "assignment_xx". You can use the second if you want to apply the algorithms directly from C. If you do not have MATLAB installed, you have to replace the mx-functions (e.g. mxCalloc) by ordinary C-functions and delete the two include lines.
If you decide to use the functions in C, you might need the column indices to start from 0, not from 1 as in MATLAB. Just delete the definition of ONE_INDEXING and you are done. If you do not need to handle infinite values in your applications, also delete the definition of CHECK_FOR_INF.
Two more points to take care of when using C: The assignment vector is defined as a double precision array, as MATLAB uses double precision values anyway. When referencing elements with the computed assignment vector in C, you have to change all function declarations to use integer values. Further, the distance or cost matrix of size MxN is defined as a double precision array of N*M elements. Matrices are saved MATLAB-internally in row-order (i.e. the matrix [1 2; 3 4] will be stored as a vector [1 3 2 4], NOT [1 2 3 4]).

### Problems

I have not tested the functions on any other system than Windows with MATLAB 6.5.1. But as I do not use any sophisticated functions or special toolboxes, I expect the functions to run on all systems without problems. If you have problems anyway, feel free to contact me.

### Contact

Dr.-Ing. Markus Buehren
Stuttgart, Germany
http://www.markusbuehren.de

### Version

Last modified 05.07.2011
Latest version on Matlab Central.